1. Field of the Invention
The present invention generally relates to the field of network communications. More specifically, the present invention relates to network traffic management including quality of service provisions.
2. Background Information
With advances in integrated circuit, microprocessor, networking and communication technologies, an increasing number of devices, in particular, digital computing devices, are continually being networked together. Devices are often first coupled to a local area network, such as an Ethernet based office/home network. In turn, the local area networks are interconnected together through wide area networks, such as Ethernet, SONET networks, ATM networks, Frame Relays, and the like. Of particular interest is the TCP/IP based global inter-network “Internet”.
As the number of devices communicating over the Internet continues to increase, the volume and complexity of the data transmitted correspondingly continues to increase. In addition, not only do many applications such as real time audio/video transmissions and application delivery services require large amounts of network bandwidth, but they may also require that certain quality parameters such as the time it takes the data to be delivered (i.e. end-to-end latency) and inter-packet delay variation (jitter), not exceed a predetermined threshold so as to adversely affect transmission quality. Service providers often guarantee differing levels of quality of service (QoS) to subscribers, with guarantees of higher quality often costing more than guarantees of a relatively lower quality or no guarantees at all (i.e. best effort).
Integrated services and differentiated services reflect two common methodologies for implementing QoS. The integrated service model is typically concerned with individual data flows and reserves network resources, employs packet classification, admission control, and intelligent scheduling to achieve a desired QoS. A data flow generally represents a stream of packets that originate from the same user activity such as an application. In contrast, the differentiated service model basically classifies packets into a small number of service types or classes of service and applies similar techniques to all traffic that belongs to the same type or class of service. Whether an integrated service model or a differentiated service model is employed within a given network, some form of packet queuing and scheduling is typically utilized throughout the various network switching and/or routing devices in order to regulate and prioritize data transmissions.
In their simplest form, single queue implementations have been utilized whereby packets were queued and transmitted on a first-come first-served basis. That is to say that the packets were basically transmitted according to their order of arrival. For example, if packets of a first packet flow (P1) arrived in the queue before packets of a second packet flow (P2), and (P2) packets arrived in the queue before packets of a third packet flow (P3), the (P1) packets would be transmitted before the (P2) packets, which in turn would be transmitted before the (P3) packets. In this single queue implementation however, if either the (P2) packets or the (P3) packets had a higher priority (i.e. were more urgent) than the (P1) packets, head-of-line blocking would occur where the (P2) packets and the (P3) packets would be blocked by the (P1) packets. Because this method caused some packets to be unnecessarily blocked by other packets, additional delays adversely affecting QoS guarantees were commonplace.
In an effort to avoid head-of-line blocking, implementations utilizing multiple packet queues have been used. In a multiple queue implementation for example, packets of each flow are placed into their own queue enabling each flow to be directly selected by e.g. a scheduling mechanism based upon the quality of service for the flow, independently of other packet flows. However, this solution does not scale very well since the time it takes to enqueue or dequeue an information packet is dependent upon the number and length of queues utilized.